package club.xiaojiawei.linkedlist;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 2022/4/24 下午6:07
 * @question 19.删除链表倒数第N个节点
 * @description 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点
 */
public class DeleteElementForLinkedList19 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        ListNode result = removeNthFromEnd(null, 4);
        System.out.println(result);
    }

    static int count = 0;

    static int index = 0;

    /**
     * 双指针 递归
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newNode = new ListNode();
        newNode.next = head;
        go(newNode, n);
        return newNode.next;
    }

    public static void go(ListNode node, int n){
        if (node == null){
            index = count;
            return;
        }
        count++;
        go(node.next, n);
        if (count - index-- == n){
            node.next = node.next.next;
        }
    }

    /**
     * 官方-栈
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    '}';
        }
    }
}
